package org.dormi.learn.algorithm;

import org.dormi.learn.definition.Graph;
import org.dormi.learn.definition.Vertex;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.List;

import static org.dormi.learn.definition.Vertex.SEQ_NOT_SET;

/**
 * @author : dormi330
 * @since : 2021/1/27/0027
 * <p>
 */
public class GraphAlgorithm {

    private static final Logger log = LoggerFactory.getLogger(GraphAlgorithm.class);

    public static void dfs(Graph g) {
        int nextStart = 0;
        if (g.getEntry() != null) {
            nextStart = dfs(g, g.getEntry(), nextStart);
        }
        for (Vertex v : g.getVertices()) {
            nextStart = dfs(g, v, nextStart);
        }
    }

    /** Depth First Search 深度优先搜索 */
    private static int dfs(Graph g, Vertex entry, int seq) {

        /* 已访问, 跳过 */
        if (entry.getArrival() != SEQ_NOT_SET) {
            return seq;
        }

        log.info("dfs, 进入节点[{}]", entry);
        entry.arrival(++seq);

        // 顶点entry的 邻接表, 第一个节点是自身
        List<Vertex> oneLine = g.getAdjMap().get(entry);
        if (oneLine.size() == 1) {
            log.info("dfs, 离开节点[{}]", entry);
            entry.departure(++seq);
            return seq;
        }

        // 递归遍历
        for (int i = 1; i < oneLine.size(); i++) {
            Vertex next = oneLine.get(i);
            if (next.getArrival() == SEQ_NOT_SET) {
                seq = dfs(g, next, seq);
            }
        }
        log.info("dfs, 离开节点[{}]", entry);
        entry.departure(++seq);
        return seq;
    }
}
